import json
from collections import defaultdict


def build_tree(data):
    def get_struct(d):
        _d = defaultdict(list)
        for a, *b in d:
            _d[a].append(b)
        return [
            {
                'title': a,
                'expanded': False,
                'children': get_struct(filter(None, b))
            } for a, b in _d.items()
        ]

    components = [i.split('-') for i in data]
    return json.loads(json.dumps(get_struct(components)))


def traverse_tree(json_tree, data):
    def traverse(json_tree, d):
        if len(d) == 0:
            return None
        a, *b = d
        for sub in json_tree:
            if sub['title'] == a:
                sub['expanded'] = True
                traverse(sub['children'], b)
        return json_tree

    return traverse(json_tree, data.split('-'))


def build_taxonomy(data):
    result_str = ''
    # data = ['a-aa-aab', 'a-aa-aaa', 'b-ba-baa', 'a-aa-aab-aaba', 'a-aa-aab-aabb']
    result = defaultdict(set)
    for string in data:
        parts = string.split('-')
        for i in range(len(parts)):
            key = '-'.join(parts[:i])
            if key == '':
                val = '-'.join(parts[:i + 3])
            elif key.count('-') == 2:
                val = '-'.join(parts[:i + 2])
            elif key.count('-') == 3:
                continue
            else:
                continue
            result[key].add(val)

    result = sorted(result.items(), key=lambda x: x[1], reverse=True)
    for prefix, children in result:
        result_str += prefix or 'root'
        for child in children:
            result_str += ' ' + child
        result_str += '\n'

    return result_str


def get_taxonomy(data):
    result = defaultdict(set)
    for string in data:
        parts = string.split('-')
        for i in range(len(parts)):
            key = '-'.join(parts[:i])
            if key == '':
                val = '-'.join(parts[:i + 3])
            elif key.count('-') == 2:
                val = '-'.join(parts[:i + 2])
            elif key.count('-') == 3:
                continue
            else:
                continue
            result[key].add(val)

    result = sorted(result.items(), key=lambda x: x[1], reverse=True)
    result_list = []
    for prefix, children in result:
        for ch in children:
            result_list.append(str(ch))
    return result_list


def get_groups(d):
    _d = defaultdict(list)
    for a, [j, *k] in d:
        _d[j].append((a, k))
    for a, b in _d.items():
        k, vals = [x for x, y in b if not y], [(x, y) for x, y in b if y]
        if k and not vals:
            yield from k
        else:
            yield from get_groups(vals)


def get_deepest_data(data):
    components = [(i, i.split('-')) for i in data]
    return list(get_groups(components))


if __name__ == '__main__':
    data = ['a-aa-aab', 'a-aa-aaa', 'a-aa-aab-aaba-aabaa', 'a-aa-aab-aabb-aabba', 'b-ba-baa']
    json_tree = build_tree(data)
    print(json_tree)

    taxonomy_str = build_taxonomy(data)
    print(taxonomy_str)

    json_tree = traverse_tree(json_tree, 'a-aa-aaa')
    print(json.dumps(json_tree))

    print('-' * 100)

    result_list = get_taxonomy(['肺纹理-数量-增多', '肺实质-密度形态-网状、细线状及条索状影-条索状', '肋膈角-轮廓-模糊-发生位置-左侧'])
    print(result_list)

    data = ['a', 'a-a', 'b', 'b-a', 'b-a-a']

    deepest_data = get_deepest_data(data)
    print(deepest_data)
